// ------------------------------------------------------------------------------------------------
// ---- Livro Algoritmos (de Cormen, Leiserson, Rivest, Stein) ------------------------------------
// ---- Problema da Multiplicacao de Cadeias de Matrizes (Capítulo 15.2) --------------------------
// ------------------------------------------------------------------------------------------------
#include <iostream>
#include <fstream>
#include <cmath>
#include <ctime>
#include <climits>
#include <windows.h>
using namespace std;


unsigned int MCM(int* p, int N, int**& s);

void imprime_Parent(int i, int j, int** s);
void imprime_matriz(int** s, int N);

// -------------------------------------------------------------
// --- MAIN ----------------------------------------------------
// -------------------------------------------------------------
int main() {
    unsigned int t1, t2;

    int N = 3;
    int p[4] = {10,100,5,50};

    int** s = NULL;
    t1 = GetTickCount();
    cout<<"Numero de multiplicacoes escalares = "<<MCM(p,N,s)<<endl<<endl;
    t2 = GetTickCount();

    imprime_Parent(0,N-1,s);
    cout<<endl<<endl<<endl;

    if (s!=NULL) {
        for (int i=0; i<N; i++) delete[] s[i];
        delete[] s;
    }
    return 0;
}


// ------------------------------------------------------------------------------------------------
// ---- ALGORITMO MCM (Multiplicação de uma Cadeia de Matrizes) -----------------------------------
// ------------------------------------------------------------------------------------------------
unsigned int MCM(int* p, int N, int**& s) {
    int i,j,k,l;
    int** m = new int*[N]; for (i=0; i<N; i++) m[i] = new int[N];
    if (s==NULL) {s=new int*[N]; for (i=0; i<N; i++) s[i] = new int[N];}

    for (i=0; i<N; i++) m[i][i] = 0;

    for (l=2; l<=N; l++) {
        for (i=0; i<N-l+1; i++) {
            j = i+l-1;
            m[i][j] = INT_MAX;
            for (k=i; k<j; k++) {
                int q = m[i][k] + m[k+1][j] + p[i]*p[k+1]*p[j+1];
                if (q < m[i][j]) {
                    m[i][j] = q;
                    s[i][j] = k;
                }
            }
        }
    }
    imprime_matriz(m, N);
    cout<<endl<<endl<<endl;
    int r = m[0][N-1];
    for (i=0; i<N; i++) delete[] m[i];
    delete[] m;
    return r;
}

void imprime_Parent(int i, int j, int** s) {
    if (i==j) {cout<<i+1; return;}

    cout<<"(";
    imprime_Parent(i, s[i][j], s);
    cout<<"*";
    imprime_Parent(s[i][j]+1, j, s);
    cout<<")";
}

void imprime_matriz(int** m, int N) {
    int i,j;
    for (i=0; i<N; i++) {
        for (j=0; j<i; j++) cout<<"- ";
        for (j=i; j<N; j++) cout<<m[i][j]<<" ";
        cout<<endl;
    }
}